package com.offer;


public class Test49 {

    public int nthUglyNumber(int n) {
        int[] dp = new int[n];

        dp[0] = 1;

        int p2 = 0, p3 = 0, p5 = 0;

        for (int i = 1; i < n; i++) {
            int d2 = dp[p2] * 2;
            int d3 = dp[p3] * 3;
            int d5 = dp[p5] * 5;

            dp[i] = Math.min(Math.min(d2, d3), d5);

            if (dp[i] == d2) p2++;
            if (dp[i] == d3) p3++;
            if (dp[i] == d5) p5++;
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        Test49 test = new Test49();
        System.out.println(test.nthUglyNumber(10));
    }

}
